package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/16 16:00
 * https://leetcode-cn.com/problems/word-ladder/
 */
public class Title127 {

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        Set<String> hash = new HashSet<>(wordList);
        //BFS队列
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Map<String, Integer> visited = new HashMap<>();
        visited.put(beginWord, 1);
        while (!queue.isEmpty()) {
            String word = queue.poll();
            int path = visited.get(word);
            //广度，从单词的相差一个字母的各个单词开始遍历
            for (int i = 0; i < word.length(); i++) {
                //替换每个单词
                char[] chars = word.toCharArray();
                //从a-z挨个替换
                for (char k = 'a'; k <= 'z'; k++) {
                    chars[i] = k;
                    String newWord = String.valueOf(chars);
                    if (newWord.equals(endWord)) {
                        return path + 1;
                    }
                    if (hash.contains(newWord) && !visited.containsKey(newWord)) {
                        visited.put(newWord, path + 1);
                        queue.offer(newWord);
                    }
                }
            }
        }
        return 0;
    }


    public static int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        Set<String> allWord = new HashSet<>(wordList);
        if (!allWord.contains(endWord)) {
            return 0;
        }
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            //本层bfs
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (int j = 0; j < word.length(); j++) {
                    for (char k = 'a'; k <= 'z'; k++) {
                        char[] chars = word.toCharArray();
                        chars[j] = k;
                        String nextWord = String.valueOf(chars);
                        if (nextWord.equals(endWord)) {
                            return steps.get(word) + 2;
                        }
                        if (!allWord.contains(nextWord)) {
                            continue;
                        }
                        allWord.remove(nextWord);
                        if (!nextWord.equals(beginWord)) {
                            queue.offer(nextWord);
                            steps.put(nextWord, steps.get(word) + 1);
                        }
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        List<String> list = Arrays.asList("hot","dot","dog","lot","log","cog");
        List<String> strings = Arrays.asList("a", "b", "c");
        int i = ladderLength1("a", "c", strings);
        System.out.println(i);
    }
}
